package 前K个高频元素;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class Solution {
    /*
    给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。
     */
    public int[] topKFrequent(int[] nums, int k) {
        // 构建一个ma怕。key存放nums的值，value存放nums出现的次数.
        // 利用堆排序进行频率的排序(时间复杂度 nlogn )

        int[] result = new int[k];
        // 统计每个数字的频次。key存放nums的值，value存放nums出现的次数.
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            Integer count = map.getOrDefault(num, 0);
            map.put(num, count+1);
        }
        int[][] element = new int[nums.length][2];
        int cnt = 0;
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            Integer key = entry.getKey();
            Integer value = entry.getValue();
            element[cnt][0] = key;
            element[cnt++][1] = value;
            System.out.println("key:"+key+", value:"+value);
        }
        // 根据频次进行堆排序，建立大根堆
        heapSort(element, element.length, result, k);
        return result;
    }

    void buildMaxHeap(int[][] element, int len) {
        for (int i = (len / 2) - 1; i >= 0; i--) {
            headAdjust(element, i, len);
        }
    }

    void headAdjust(int[][] element, int k, int len) {
        int tempNum = element[k][1];
        int tempCnt = element[k][0];
        for (int i = 2 * k + 1; i < len; i = i * 2 + 1) {
            if (i + 1 < len && element[i + 1][1] > element[i][1])
                i++;
            if (tempNum >= element[i][1])
                break;
            else {
                element[k][1] = element[i][1];
                element[k][0] = element[i][0];
                k = i;
            }
        }
        element[k][1] = tempNum;
        element[k][0] = tempCnt;
    }

    void heapSort(int[][] element, int len, int[] result, int k) {
        buildMaxHeap(element, len);
        for (int i = 0; i < k; i++) {

            result[i] = element[0][0];

            int tempNum = element[0][1];
            int tempCnt = element[0][0];
            element[0][1] = element[len - i - 1][1];
            element[0][0] = element[len - i - 1][0];
            element[len - 1][1] = tempNum;
            element[len - 1][0] = tempCnt;
            headAdjust(element, 0, len - 1);
        }
    }
}
